package com.example.Arithmetic.Arithmetic;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;


/**
 * 日期：2023/10/15
 * 时间：11:10
 * 描述：二叉搜索树
 */
public class BSTTree<K extends Comparable<K>, V> {
    public BSTNode<K, V> root;

    public static class BSTNode<K, V> {
        private K key;
        private V value;
        private BSTNode<K, V> left;
        private BSTNode<K, V> right;

        public BSTNode(K key) {
            this.key = key;
        }

        public BSTNode(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public BSTNode(K key, V value, BSTNode left, BSTNode right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * @param key
     * @return 结果集
     * Queries elements smaller than the given key
     * 查询比给定key小的元素
     */
    public List<V> less(K key) {
        List<V> list = new ArrayList<>();
        LinkedList<BSTNode> linkedList = new LinkedList();
        BSTNode node = root;
        while (node != null || !linkedList.isEmpty()) {
            if (node != null) {
                linkedList.push(node);
                node = node.left;
            } else {
                BSTNode<K, V> pop = linkedList.pop();
                int i = pop.key.compareTo(key);
                if (i == -1) {
                    list.add(pop.value);
                } else {
                    break;
                }
                node = pop.right;
            }
        }
        return list;
    }

    /**
     * @param key
     * @return 结果集
     * Queries elements larger than the given key
     * 查询比给定key大的元素
     */
    public List<V> greater(K key) {
        List<V> list = new ArrayList<>();
        LinkedList<BSTNode> linkedList = new LinkedList();
        BSTNode node = root;
        while (node != null || !linkedList.isEmpty()) {
            if (node != null) {
                linkedList.push(node);
                node = node.right;
            } else {
                BSTNode<K, V> pop = linkedList.pop();
                int i = pop.key.compareTo(key);
                if (i > 0) {
                    list.add(pop.value);
                } else {
                    break;
                }
                node = pop.left;
            }
        }
        return list;
    }

    /**
     * @param key1
     * @param key2
     * @return 结果集
     * Queries the elements between the given two numbers
     * 查询给定两个数之间的元素
     */
    public List<V> between(K key1, K key2) {
        List<V> list = new ArrayList<>();
        LinkedList<BSTNode> linkedList = new LinkedList();
        BSTNode node = root;
        while (node != null || !linkedList.isEmpty()) {
            if (node != null) {
                linkedList.push(node);
                node = node.left;
            } else {
                BSTNode<K, V> pop = linkedList.pop();
                int i = pop.key.compareTo(key1);
                int j = pop.key.compareTo(key2);
                if (i > 0 && j < 0) {
                    list.add(pop.value);
                } else if (j > 0) {
                    break;
                }
                node = pop.right;
            }
        }
        return list;
    }

    /**
     * @param key
     * @return V
     * Recursion delete
     * 递归删除
     */
    public V ddelete(K key) {
        List list = new ArrayList();
        root = dodelete(root, key, list);
        return !list.isEmpty() ? (V) list.get(0) : null;
    }

    private BSTNode dodelete(BSTNode<K, V> node, K key, List list) {
//        结束条件
        if (node == null) {
            return null;
        }
        //递归调用寻找删除节点和进行删除和赋值
        int i = node.key.compareTo(key);
        if (i < 0) {
            node.left = dodelete(node.left, key, list);
            return node;
        }
        if (i > 0) {
            node.right = dodelete(node.right, key, list);
            return node;
        }
        list.add(node.value);
//      只有右孩子
        if (node.left == null) {
            return node.right;
        }
//      只有左孩子
        if (node.right == null) {
            return node.left;
        }
//        寻找后继节点
        BSTNode s = node.right;
        while (s.left != null) {
            s = s.left;
        }
//        给后继节点赋值
//        递归得到右节点的右子树
        s.right = dodelete(node.right, key, new ArrayList());
        s.left = node.left;
        return s;
    }


    /**
     * @param key
     * @return V
     * 根据key删除值
     * Delete values based on key
     */
    public V delete(K key) {
//        p指向即将被删除的节点
        BSTNode<K, V> p = root;
//        记录最近一个左节点
        BSTNode<K, V> parent = null;
        while (p != null) {
            int i = p.key.compareTo(key);
            if (i < 0) {
                parent = p;
                p = p.left;
            } else if (i > 0) {
                parent = p;
                p = p.right;
            } else {
                break;
            }
        }
        if (p == null) {
            return null;
        }
//        删除操作

//        前两种情况
//        删除节点没有右孩子，把左孩子托孤给parent
        if (p.left != null && p.right == null) {
            shift(parent, p, p.left);
//        删除节点没有左孩子，把右孩子托孤给parent
        } else if (p.left == null && p.right != null) {
            shift(parent, p, p.right);
            return null;

//       情况4，左右都有孩子
        } else {
//            寻找删除节点后继节点
//           deQueen 右孩子中寻找最小后继节点
//           deParent 记录后继节点的爹
            BSTNode deQueen = p.right;
            BSTNode deParent = p;
            while (deQueen.left != null) {
                deParent = deParent;
                deQueen = deQueen.left;
            }
//            删除节点和后继节点爹不相邻
            if (p != deParent) {
//               能到这里就不可能有左孩子
//                使后继父亲的左节点指向后继节点的右节点
                shift(deParent, deQueen, deQueen.right);
//             删除后使指针指向后继节点右节点
                deQueen.right = root.right;
            }
            shift(parent, p, deQueen);
            deQueen.left = p.left;
        }
        return p.value;
    }

    /**
     * @param parent  被删除节点的父节点
     * @param deleted 被删除节点
     * @param child   即将被顶上去的节点
     *                Entrust an orphan on sb.
     *                托孤方法
     */
    private void shift(BSTNode parent, BSTNode deleted, BSTNode child) {
        if (parent == null) {
            this.root = child;
        } else if (parent.left == deleted) {
            parent.left = child;
        } else {
            parent.right = child;
        }
    }

    /**
     * @return V
     * 找到上一个前驱节点
     * Find the previous precursor node
     */
    public V predecessor(K key) {
        BSTNode<K, V> p = root;
//        记录最近一个左节点
        BSTNode<K, V> b = null;
        while (p != null) {
            int i = p.key.compareTo(key);
            if (i < 0) {
                p = p.left;
            } else if (i > 0) {
                b = p;
                p = p.right;
            } else {
                break;
            }
        }
//        没找到
        if (p == null) {
            return null;
        }
//        有左孩子
        if (p.left != null) {
            return MaxValue(p.left);
        }
//        找最近的靠左父节点
        if (b != null) {
            return b.value;
        }
        return null;
    }

    /**
     * @return V
     * 找到上一个后继节点
     * Find the previous successor node
     */
    public V successor(K key) {
        BSTNode<K, V> p = root;
//        记录最近一个右节点
        BSTNode<K, V> b = null;
        while (p != null) {
            int i = p.key.compareTo(key);
            if (i < 0) {
                b = p;
                p = p.left;
            } else if (i > 0) {
                p = p.right;
            } else {
                break;
            }
        }
//        没找到
        if (p == null) {
            return null;
        }
//        有右孩子
        if (p.right != null) {
            return MinValue(p.right);
        }
//        找最近的靠右父节点
        if (b != null) {
            return b.value;
        }
        return null;
    }


    /**
     * @param key
     * @param value
     * @return boolean
     * 插入一个新值
     * insert a new value
     */
    public boolean put(K key, V value) {
        if (key == null || value == null) {
            return false;
        }
        BSTNode<K, V> node = root;
        BSTNode<K, V> parent = null;
        while (node != null) {
            parent = node;
            int i = node.key.compareTo(key);
            if (i < 0) {
                node = node.left;
            } else if (i > 0) {
                node = node.right;
//                找到值，更新
            } else {
                node.value = value;
                return true;
            }
        }
//        未找到，插入
        if (parent == null) {
            root = new BSTNode(key, value);
            return true;
        }
        int i = parent.key.compareTo(key);
        if (i <= 0) {
            parent.left = new BSTNode<>(key, value);
        } else {
            parent.right = new BSTNode<>(key, value);
        }
        return true;
    }

    /**
     * @return V
     * 获取二叉树最小值
     * Gets the minimum value of the binary tree
     */
    public V MinValue() {
        return MinValue(this.root);
    }

    private V MinValue(BSTNode root) {
        if (root == null) {
            return null;
        }
        BSTNode<K, V> bstNode = root;
        while (bstNode.left != null) {
            bstNode = bstNode.left;
        }
        return bstNode.value;
    }


    /**
     * @return V
     * 获取二叉树最大值
     * Gets the maximum value of the binary tree
     */
    public V MaxValue() {
        return MaxValue(this.root);
    }

    private V MaxValue(BSTNode root) {
        if (root == null) {
            return null;
        }
        BSTNode<K, V> bstNode = root;
        while (bstNode.right != null) {
            bstNode = bstNode.right;
        }
        return bstNode.value;
    }

    /**
     * @param key
     * @return V
     * <p>根据key获取值</p>
     */
    public V Get(K key) {
        if (key == null) {
            return null;
        }
        BSTNode<K, V> bstNode = root;
        while (bstNode != null) {
            int i = bstNode.key.compareTo(key);
            if (i < 0) {
                bstNode = bstNode.left;
            } else if (i > 0) {
                bstNode = bstNode.right;
            } else {
                return bstNode.value;
            }
        }
        return null;
    }

    /**
     * @param root
     * @param key
     * @return V
     * This method is used for recursive fetching
     * 此方法用于递归获取
     */
    private V DoGet(BSTNode<K, V> root, K key) {
        if (root == null) {
            return null;
        }
        int i = root.key.compareTo(key);
        if (i < 0) {
            return DoGet(root.left, key);
        } else if (i > 0) {
            return DoGet(root.right, key);
        } else {
            return root.value;
        }
    }
}
